8.1 排序基本概念
稳定性
分类
8.2 插入与希尔
8.2.1 插入排序
代码实现
每次将大于待插入元素的前面的元素后移一位，再将待插入元素移入空出的位置：  空间复杂度：O(1)，时间复杂度：O(n^2)，稳定。在待排序的记录基本有序的时候，时间复杂度能达到O(1)的级别。
优化
在待插入元素的前面的部分是有序的，可以使用折半查找优化：    此时low在high的右侧，停止折半查找，high右侧的元素均大于i所指元素，low左侧则均小于。在low和high中间的位置就是待插入元素的插入位置：  特殊的，在这种情况下，不应该停止查找，而应该是在右侧继续寻找60，确保算法的稳定性：   这时，插入60就能够保证算法的稳定性：  
8.2.2 希尔排序
将表中的元素拆分为多个子表，将子表中的元素排序，最后整体有序。
    在这一次排序中，表中的数据就已经基本有序：  
代码实现
 空间复杂度：O(1)，时间复杂度：在O(n^1.3)到O(n^2)，暂时无法用数学形式证明。不稳定。并且只能基于线性表实现。
8.3 交换排序
8.3.1 冒泡排序
   
算法实现
若某一趟排序过程没有交换，就说明已经有序，可以提前结束： 
空间复杂度：O(1)，时间复杂度：O(n^2)，稳定。 
8.3.1 快速排序
      将基准元素左右两侧的子表继续快排，直到左右子表就剩一个元素的时候
代码实现（重点）
空间复杂度：O(递归层数)，时间复杂度：O(n * 递归层数)，不稳定。递归层数的数量级在log n与n之间。理想情况下，空间复杂度：O(log n)，时间复杂度：O(nlog n) 
对于本有序的序列，快排的性能最差。可以随机选取枢轴元素来解决这个问题。
8.4 选择排序
8.4.1 简单选择排序（暴力）
在待排序的元素中选着最小的加入有序队列
代码实现
 空间复杂度：O(1)，时间复杂度：O(n^2)，不稳定。
8.4.2 堆排序
 被选出的堆顶元素，就不会再继续参与排序（已确定）
代码实现
 建堆过程时间复杂度：O(n)，排序整体时间复杂度：O(nlog n)，空间复杂度：O(1)，不稳定
堆
 逻辑上是一棵顺序存储的完全二叉树，大根堆就是根节点大于左右子树。
将初始的序列建立为一个大根堆，再使用选择排序就能提高效率。 
堆的代码实现
堆插入与删除
 
8.5
8.5.1 归并排序
代码实现
 时间复杂度：O(nlog n)，空间复杂度：O(n)（其中包括辅助数组n和递归栈所占用的空间log n），稳定的。
归并
将多个有序的序列合并 
考试通常是二路，手算。上例是二路归并，下面为四路： 
8.5.2 基数排序
将关键字的每个位数取出排序后，再取高位再排序，直到全部的位都被排序过        通常基于链式存储实现，空间复杂度：O(每位可能取值的个数)，时间复杂度：O(分配的次数 * (关键字的位数 + 每位可能取值的个数))，稳定的。
对于要排序的数据可以拆分、分组不太多的时候时候使用： 
8.5.3 计数排序
8.7 外部排序
8.7.1 基础概念
构造初始归并段
将第一块与第二块的内容读入内存，进行内部排序，再写入内存变为一个归并段： 
第一趟归并
将归并段进行归并：  
第二趟归并
时间开销分析
 时间开销=读写时间+排序时间（构造初始归并段）+归并时间
减少归并的次数就能减少读写的时间： 
8.7.2 败者树
 使用多路归并时，对比的次数会变多，可以使用败者树优化
  初始构造时对比k-1次，之后使用败者树最少可以对比log k向上取整的次数，比k-1要少的多
8.7.3 置换-选择排序
优化构造初始归并段的过程，来构建更长的初始归并段： 
将比minmax更大的最小值输出，直到wa中不能再输出，就生成一个新的归并段： 
8.7.4 最佳归并树
使用置换-选择排序算法生成的归并段长度不一，每次都要读写每个段的长度： 
使用哈夫曼树来得到wpl最小的树： 
构造3路归并的最佳归并树： 
如果无法构造k叉归并树：  